package sjg.DataStructures.linkedList;

import java.util.Stack;

/**
 * 单链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "林冲", "豹子头");
        HeroNode hero3 = new HeroNode(3, "卢俊义", "玉麒麟");
        HeroNode hero4 = new HeroNode(4, "吴用", "智多星");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        System.out.println("从最后插入，并且没有根据 编号[no]字段 去重");
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList.list();

//        System.out.println("测试del方法");
//        singleLinkedList.del(hero1);
//        singleLinkedList.del(hero4);
//        singleLinkedList.list();

//        System.out.println("测试update方法");
//        hero3.name = "hero2";
//        hero3.nickname = "hero2_nickname";
//        singleLinkedList.update(hero3);
//        singleLinkedList.list();

//        System.out.println("测试addByOrder方法");
//        singleLinkedList.addByOrder(hero1);
//        singleLinkedList.addByOrder(hero2);
//        singleLinkedList.addByOrder(hero4);
//        singleLinkedList.addByOrder(hero3);
//        singleLinkedList.addByOrder(hero1);
//        singleLinkedList.addByOrder(hero2);
//        singleLinkedList.list();


//        System.out.println("大厂面试题: 单链表");
//
//        System.out.println("测试getLength方法，获取带节点的单链表节点个数");
//        int length = singleLinkedList.getLength(singleLinkedList.getHead());
//        System.out.println("该单链表节点个数为：" + length);
//
//        System.out.println("测试: 根据下标倒序获取单链表值");
//        HeroNode nodeByIndex = singleLinkedList.getNodeByIndex(singleLinkedList.getHead(), 0);
//        System.out.println(nodeByIndex == null ? null : nodeByIndex.toString());

//        System.out.println("测试链表反转");
//        singleLinkedList.reverseList(singleLinkedList.getHead());
//        singleLinkedList.list();


        System.out.println("测试 —— 逆序打印方式二");
        singleLinkedList.reversePrint(singleLinkedList.getHead());

//        System.out.println("测试 —— 逆序打印方式一");
//        singleLinkedList.reversePrint1(singleLinkedList.getHead());

//        System.out.println("测试 —— 两个单链表合并，保持有序，从小到大");
//        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
//        HeroNode hero5 = new HeroNode(0, "宋江", "及时雨");
//        HeroNode hero6 = new HeroNode(5, "林冲", "豹子头");
//        HeroNode hero7 = new HeroNode(6, "卢俊义", "玉麒麟");
//        HeroNode hero8 = new HeroNode(7, "吴用", "智多星");
//        singleLinkedList2.add(hero5);
//        singleLinkedList2.add(hero6);
//        singleLinkedList2.add(hero7);
//        singleLinkedList2.add(hero8);
//        HeroNode heroNode = singleLinkedList2.mergeTwoLinkedList(singleLinkedList.getHead(), singleLinkedList2.getHead());
////        HeroNode heroNode = singleLinkedList2.mergeTwoLinkedList(null, null);
//        // 遍历打印检查结果
//        while (heroNode != null) {
//            System.out.println(heroNode.toString());
//            heroNode = heroNode.next;
//        }


    }
}

// 定义 SingleLinkedList 管理我们的英雄
class SingleLinkedList {
    // 初始化一个头节点
    private HeroNode head = new HeroNode(0, "", "");

    // 返回头节点
    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点到单向链表
     * 当不考虑编号顺序时，找到当前链表的最后节点，将最后节点的next指向新节点
     */
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，因此需要一个辅助遍历temp
        HeroNode temp = head;
        while (temp.next != null) {
            // 链表的最后
            // 如果没有找到，就将temp后移
            temp = temp.next;
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 将最后这个节点的next指向新节点
        temp.next = heroNode;
    }

    /**
     * 有序插入
     * 第二种方式：在添加英雄时，根据排名将英雄插入到指定位置
     * 如果有这个排名，则添加失败，并给出提示
     */
    public void addByOrder(HeroNode heroNode) {
        // mine 一种写法
        HeroNode temp = head;
        // 空链表直接添加
        if (temp.next == null) {
            temp.next = heroNode;
            return;
        }
        while (temp.next != null) {
            // 匹配到值，直接返回，已经有值，禁止插入
            if (temp.next.no == heroNode.no) {
                System.out.printf("准备插入的英雄编号 %d 已经存在了，不可插入！\n", heroNode.no);
                return;
            }
            // 匹配不到值，且最后一位为空
            if (temp.next.no < heroNode.no && temp.next.next == null) {
                temp.next.next = heroNode;
                return;
            }
            // 匹配不到值，且处于中间位置
            if (temp.next.no < heroNode.no && temp.next.next.no > heroNode.no) {
                heroNode.next = temp.next.next;
                temp.next.next = heroNode;
                return;
            }
            temp = temp.next;
        }

//        // other
//        HeroNode temp = head;
//        boolean flag = false; // flag 标志添加的编号是否存在，默认为false
//        while (true) {
//            if (temp.next == null) { // 说明temp已经在链表最后了
//                break;
//            }
//            if (temp.next.no > heroNode.no) {// 位置找到，就在temp后面插入
//                break;
//            } else if (temp.next.no == heroNode.no) { // 说明希望添加的heroNode已经存在
//                flag = true; // 编号已经存在
//                break;
//            }
//            temp = temp.next;
//        }
//        // 判断flag的值
//        if (flag) {
//            System.out.printf("准备插入的英雄编号 %d 已经存在了，不可插入！\n",heroNode.no);
//        }else{
//            // 插入到链表中temp后面
//            heroNode.next=temp.next;
//            temp.next = heroNode;
//        }
    }

    // 根据heroNode的节点值进行删除
    public void del(HeroNode heroNode) {
        // 判空
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        // 遍历
        HeroNode temp = head;
        while (temp.next != null) {
            // 匹配
            if (temp.next.no == heroNode.no || temp.next.name.equals(heroNode.name) || temp.next.nickname.equals(heroNode.nickname)) {
                // 删除
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 修改 - 根据 no
     */
    public void update(HeroNode heroNode) {
        // 判空
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        // 遍历
        HeroNode temp = head;
        while (temp.next != null) {
            // 匹配
            if (temp.next.no == heroNode.no) {
                // 修改
                temp.next.name = heroNode.name;
                temp.next.nickname = heroNode.nickname;
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 遍历链表展示
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    /**
     * 求单链表节点个数
     */
    public int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode temp = head;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * 获取倒数个数的节点，入参：输出的倒数节点位置数值
     */
    public HeroNode getNodeByIndex(HeroNode head, int goal) {
        // 统计单链表总长度
        int size = getLength(head);
        // 判断长度是否符合
        if (size < goal || goal <= 0) {
            System.out.println("该节点长度超过区间或者<=0!");
            return null;
        }
        int x = 0;
        int goalVal = size - goal + 1; // 目标位置
        HeroNode temp = head;
        while (true) {
            temp = temp.next;
            x++;
            if (x == goalVal) {
                return temp;
            }
        }
    }

    /**
     * 单链表反转
     * 思路：
     * 新建一个头结点
     * 遍历原始链表，依次将值插入新链表第一个位置
     * 将原始链表头结点指向新链表头结点下个位置。
     */
    public void reverseList(HeroNode head) {
        // 如果当前链表为空或只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        // 定义一个辅助的指针(变量)，帮助我们遍历原有的链表
        HeroNode cur = head.next;
        HeroNode next = null; //指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");

        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur != null) {
            next = cur.next;// 先暂时保存一下当前节点的下个结点，因为后面需要
            cur.next = reverseHead.next;// 将cur的下一个节点指向新链表的最前端
            reverseHead.next = cur;// 将cur连接到新链表上
            cur = next; // 将cur后移
        }

        // 将head.next指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }

    /**
     * 逆序打印单链表
     * 方式一：反转单链表，然后打印 —— 破坏了链表结构，不可取
     * 方式二：使用栈 数据结构，利用它先进后出的特点从栈顶依次取值，达到逆序打印的目的。
     * <p>
     * 以下代码是方式二
     */
    public void reversePrint(HeroNode head) {
        // 判空
        if (head.next == null) {
            System.out.println("链表为空~~~");
        }
        HeroNode temp = head;
        Stack<HeroNode> stack = new Stack<>();
        while (temp.next != null) {
            // 压栈
            stack.push(temp.next);
            temp = temp.next;
        }

        // 出栈 - 逆序打印
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 逆序打印单链表
     * 方式一：反转单链表，然后打印 —— 破坏了链表结构，不可取
     * 方式二：使用栈 数据结构，利用它先进后出的特点从栈顶依次取值，达到逆序打印的目的。
     * <p>
     * 以下代码是方式一
     */
    public void reversePrint1(HeroNode head) {
        // 判断是否可以逆序
        if (head.next == null || head.next.next == null) {
            System.out.println("链表为空或长度为1，不必逆序~");
        }
        // 单链表倒序
        HeroNode temp = head.next;
        HeroNode temp2 = new HeroNode(0, "", "");
        HeroNode a;
        while (temp != null) {
            // 每次处理一个 node
            // 作为临时变量承接 temp  ==> temp作为一个无头节点单链表，每次遍历少一个node
            a = temp.next;
            // 将目标node拼接到temp最前端
            temp.next = temp2.next;
            // temp 加上头结点
            temp2.next = temp;
            // 将临时变量值去掉一个，然后重新赋值给temp
            temp = a;
        }
        // 对新的单链表遍历
        while (temp2.next != null) {
            System.out.printf("%s\n", temp2.next.toString());
            temp2 = temp2.next;
        }
    }

    /**
     * 合并两个有序链表，合并之后依然有序
     * 145  236
     * 123456
     * 假设是这样，从小到大排序
     */
    public HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
        // 默认比大小
        // 判断是否有排序的必要
        // 防止空指针，确定有next node，要不后续处理直接空指针
        if (head1 == null && head2 == null) {
            System.out.println("第一个第二个链表为null~没有头结点！");
            return null;
        } else if (head1 == null && head2 != null) {
            return head2;
        } else if (head1 != null && head2 == null) {
            return head1;
        }

        HeroNode temp1 = head1;
        HeroNode temp2 = head2;
        HeroNode targetHead = new HeroNode(0, "", "");
        HeroNode targetHead2 = targetHead;
        while (true) {
            if (temp1.next != null && temp2.next != null) {
                if (temp1.next.no <= temp2.next.no) {
                    targetHead2.next = temp1.next;
                    targetHead2 = targetHead2.next;
                    temp1.next = temp1.next.next;
                    continue;
                } else {
                    targetHead2.next = temp2.next;
                    targetHead2 = targetHead2.next;
                    temp2.next = temp2.next.next;
                    continue;
                }
            }
            // 到这里已经只剩下一条链表了，直接循环添加处理
            while (temp1.next != null) {
                targetHead2.next = temp1.next;
                targetHead2 = targetHead2.next;
                temp1.next = temp1.next.next;
                break;
            }
            while (temp2.next != null) {
                targetHead2.next = temp2.next;
                targetHead2 = targetHead2.next;
                temp2.next = temp2.next.next;
                break;
            }
            if (temp1.next == null && temp2.next == null) {
                break;
            }
        }
        return targetHead;
    }

}

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    // 为了显示，重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
